package exercises.leetcode;

import exercises.newcoder.util.TreeNode;

/**
 * <a href="https://leetcode-cn.com/problems/validate-binary-search-tree/">
 * 98. 验证二叉搜索树</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <ol>
 * <li>节点的左子树只包含 小于 当前节点的数。</li>
 * <li>节点的右子树只包含 大于 当前节点的数。</li>
 * <li>所有左子树和右子树自身必须也是二叉搜索树。</li>
 * </ol>
 * 示例 1：
 * <p>
 * 输入：root = [2,1,3]
 * 输出：true
 * <p>
 * 示例 2：
 * <p>
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 * <p>
 * 提示：
 * <li>树中节点数目范围在[1, 104] 内</li>
 * <li>-231 <= Node.val <= 231 - 1</li>
 *
 * @author or2
 * @date 2021年10月02日 时间: 9:07
 */
public class No98 {
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;

        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode root, long minValue, long maxValue) {
        if (root == null)
            return true;
        if (root.val <= minValue || root.val >= maxValue)
            return false;
        if (!isValidBST(root.left, minValue, root.val))
            return false;
        return isValidBST(root.right, root.val, maxValue);
    }
}
